/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
	typedef ListNode* ListNodePtr;
	struct Cmp {
		bool operator()(const ListNodePtr& a, const ListNodePtr& b) const {
			return a->val > b->val;
		}
	};

    ListNode *mergeKLists(vector<ListNode *> &lists) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
		ListNode* cur = NULL;
		ListNode* head = NULL;
		vector<ListNode*> q;

		for (int i = 0; i < lists.size(); ++i) {
			if (lists[i] != NULL) {
				q.push_back(lists[i]);
			}
		}

		make_heap(q.begin(), q.end(), Cmp());
		while (!q.empty()) {
			ListNode* top_head = q[0];
			pop_heap(q.begin(), q.end(), Cmp());
			q.pop_back();

			if (head == NULL) {
				head = top_head;
				cur = top_head;
			} else {
				cur->next = top_head;
				cur = top_head;
			}
			if (top_head->next != NULL) {
				q.push_back(top_head->next);
				push_heap(q.begin(), q.end(), Cmp());
			}
		}
		return head;
    }
};
